The invention pertains to a self-contained navigation system that can be used by self-propelled, fully automatic vehicles. As such, it is not intended as a complete solution but as a critical component of a larger system. The disclosed invention allows automated machines to do such simple, repetitive tasks as lawn mowing, snow removal, excavation, surveying, sentry duty and mine sweeping. The vehicle must be trained to execute the intended task, but can operate unattended thereafter.
Autonomous mobile devices have been fashioned with a variety of techniques. All must solve the problem of traversing a terrain efficiently and accurately.
Many devices are specifically adapted for highly conditioned environments, e.g. building corridors, and assume, say, that the device is moving on a flat level surface, that the work area is bounded walls, or other such cues. Devising autonomous vehicles that work outdoors in a natural environment is more challenging.
Several categories of autonomous vehicles rely on conditioning the environment in the target area of the device with navigational cues.
An early outdoors model (U.S. Pat. No. 4,133,404, Griffin, 1979) is an autonomous lawn mowing device which utilizes optical sensors to detect the cut/uncut lawn boundary, and uses this boundary as a navigation tool. Beyond the obvious limitation that the cut/uncut boundary must be well defined, this device requires that the boundary of the lawn to be cut manually previous to each use. A refinement of this method (U.S. Pat. No. 5,007,234, Shurman, 1991) which, however, has the same limitations, is to detect the cut/uncut boarder via the resistance of the lawn to cutting (motor speed). There is also a slow-moving solar-powered version (U.S. Pat. No. 5,444,965, Colens, 1995) which requires the mower to be continuously present in the yard to be mowed. These devices are application specific, in other words, the navigational cue is derived from the purpose of the vehicle.
A more general-purpose method of environment conditioned guidance (U.S. Pat. No. 4,777,785, Rafaels, 1988) depends on having a fixed array of transmitters or beacons pre-positioned in the target area. The number of required transmitters was reduced to three (U.S. Pat. No. 5,974,347, Nelson, 1999) in a version in which the vehicle followed a programmed path of position points. Maintenance of the system is a problem whether the transmitters are left in place between device operations, or are reinstalled prior to each use.
Another common method of environment conditioned guidance is (U.S. Pat. No. 5,163,273, Wojtkowski, 1992) to have the vehicle follow a buried wire. This method entails a large capital cost and yields little flexibility. A version (U.S. Pat. No. 4919,224) with only a guide wire around the boundary of the operational area has less installation cost, but at the expense of efficiency of traversal. Buried metal objects have also been used by Noonan et al. (U.S. Pat. No. 4919,224) as positioning and turn guides.
All these methods involve installation of permanent structures. In general, if the environment is not to be conditioned, then devising an autonomous vehicle that functions outdoors in a natural environment represents another level of complexity, since the area of operation is fundamentally three dimensional. Specifically, the motion space of the vehicle is two dimensional, being confined by gravity to the earth""s surface, while the navigation space is three dimensional, with an additional two dimensional orientation space.
A device which depends only on the motion space is possible, but prone to error. Chen (U.S. Pat. No. 4,694,639, 1987) offers a simple autonomous lawn mower with no external apparatus and no sensors. The mower follows a learning track made on paper tape. Since no provision is made for error correction, this version requires exact propositioning and even then would be restricted to a very small area of operation.
The autonomous vehicle in a non-conditioned environment must have the ability to
1. determine its current position
2. determine its desired position
3. determine how to move during the next movement segment to effect the desired change.
Several modern systems, for instance Gudat et al. (U.S. Pat. No. 5,838,562, 1998), use a Global Positioning System for navigation. However, even the best Global Positioning System is only accurate to about 5 meters. Good enough to know where you are to within a city block, but not good enough to avoid obstacles or repeat a path with any accuracy.
Another expensive and complicated solution is to use computer vision, for example (U.S. Pat. No. 5,155,684 Burke, 1992). Vision based systems have trouble with atmospheric conditions. What might appear as a sharp point of light on a cold night is a fuzzy patch of light on a hazy summer afternoon. The haze caused by humidity can make resolving landmarks with any accuracy very difficult.
The invention uses three onboard sensor groups for navigation. The first of these sensors measures the distance traveled by the vehicle along its forward axis. The second and third sensor groups detect the earth""s magnetic and gravitational fields. Because the orientation sensors make use of naturally occurring phenomena, this invention does not require externally placed emitters or buried objects, or environmental conditioning of any kind. The invention is also an improvement on vision based systems because the relatively rugged and inexpensive sensor configuration is sufficient for training and normal operation of the vehicle. Once the sensor information is collected, the on-board computer needs only a few simple, linear mathematical operations to know the vehicle""s precise location in three dimensions at all times. Training the vehicle is no more difficult than mowing a lawn. The invention is more flexible than designs that use artificial landmarks and is considerably less complicated and more reliable than vision based systems.
The invention is a means of navigation that allows a vehicle to autonomously repeat the path taught to it. The essential components are: a set of three sensors, a computer and a drive system. The vehicle must be trained to recognize the target path by an operator. After being trained, the vehicle can autonomously direct itself over the same path.
Mechanically, the invention has two independent driving wheels that are controlled by the computer. For balance and distance measurement, at least one non-driving wheel is needed. This wheel is attached to the chassis with a caster to give it two planes of freedom. The measurement of the rotation of this passive wheel is the basis for an exact measurement of the distance traveled by the vehicle. The driving wheels are subject to slipping and can""t be use for this purpose. The exact configuration of wheels is unimportant as long as the platform is stable and the vehicle can turn effectively. The independent driving wheels effect forward, backward and rotational locomotion. The passive wheel has a set of two optical shaft encoders attached to it. An absolute shaft encoder measures the angle of the axis of the passive wheel with respect to the chassis. An incremental shaft encoder is mounted on the chassis and connected to the non-driving wheel""s axis using a flexible shaft. An exact measurement of the distance traveled by the vehicle with respect to the ground is made by knowing the angle of the caster and the rotation of this wheel.
A three axis magnetometer measures the direction and magnitude of the Earth""s magnetic field. That is, three magnetometers are positioned at orthogonal angles to provide a three dimensional vector that gives the direction of the naturally occurring field. It""s not necessary that the sensors give the exactly direction to the magnetic North Pole. The important requirement is that the directional vector is constant and repeatable with respect to the Earth. This obviates the need for any special calibration.
A three axis accelerometer measures the direction and magnitude of the force of gravity. It is constructed from a set of three accelerometers positioned at orthogonal angles. Like the magnetometers, the important aspect of this sensor is that it gives a repeatable vector that is constant with respect to Earth. An unwanted side-effect of accelerometers for this application is that they also measure any inertial change in the vehicle. However, using the information from the optical shaft encoders attached to the vehicle""s wheels, the effects of inertial changes can be cancelled from the sensor yielding a constant gravitational vector.
The autonomous vehicle is trained by an operator who directs the motion either by actuators mounted directly on the device or by using a remote control. This can be over any arbitrary terrain. For the algorithm to work, the vehicle must have a common starting point for both training and unattended operation. This marker can be as simple as a visual indicator on the ground or an iron bar buried in the ground that the vehicle detects with the magnetometers. During the training pass, the vehicle collects the sensory information at regular sampling intervals and stores this data in a sensor log. The sensor log contains: the distance traveled since the last sample, the three components of the magnetic vector and the three components of the gravitational vector. This stored information is sufficient to construct a three dimensional map of the subject terrain using relatively simple linear math formulas.
During unattended operation of the vehicle, the same formulas are used with the current sensor data to calculate the current location. The difference between the internal map and the current location generates an error signal. This signal is used to direct the proportion and direction of the power delivered to the driving wheels, keeping the vehicle on the predetermined path.